#include <bits/stdc++.h>

using namespace std;

// 最优账单平衡
// 给你一个表示交易的数组 transactions
// 其中 transactions[i] = [fromi, toi, amounti]
// 表示 ID = fromi 的人给 ID = toi 的人共计 amounti
// 请你计算并返回还清所有债务的最小交易笔数
// 测试链接 : https://leetcode.cn/problems/optimal-account-balancing/

class Solution 
{
public:
    static const int MOD = 1000000007;

    // 题目说了人员编号的最大范围：0 ~ 12
	static const int MAXN = 13;

    vector<int> depts(vector<vector<int>>& transactions)
    {
        int help[MAXN];
        memset(help, 0, sizeof help);
        for(auto& tran : transactions)
        {
            help[tran[0]] -= tran[2];
            help[tran[1]] += tran[2];
        }
        int n = 0;
        for(int num : help)
        {
            if(num != 0) ++n;
        }

        vector<int> dept(n);
        int index = 0;
        for(int num : help)
        {
            if(num != 0) dept[index++] = num;
        }
        return dept;
    }

    // 参数是 set 是某个集合，在集合中用 1 来表示
    // 返回值是集合拆分出累加和是 0 的不可拆分小集合的最大数量
    // 不可拆分的小集合的意思是：该集合的累加和为 0，且非空真子集
    // 的和都不为 0。比如：{-2, -2, 4} 就是不可拆分的小集合
    int f(vector<int>& dept, int set, int sum, int n, int* dp)
    {
        if(dp[set] != -1) return dp[set];
        
        int ans = 0;
        // 集合中不只一个元素
        // 如果集合中只有一个元素，则无法划分成总和为0的子集合
        if((set & (set - 1)) != 0)
        {
            if(sum == 0)
            {
                for(int i = 0; i < n; ++i)
                {
                    if((set & (1 << i)) != 0)
                    {
                        // 找到任何一个元素，去除这个元素
						// 剩下的集合进行尝试，返回值 + 1
                        ans = f(dept, set ^ (1 << i), sum - dept[i], n, dp) + 1;
                        // 然后不需要再尝试下一个元素了，因为答案一定是一样的
						// 所以直接break
                        break;
                    }
                }
            }
            else
            {
                for(int i = 0; i < n; ++i)
                {
                    if((set & (1 << i)) != 0)
                    {
                        ans = max(ans, f(dept, set ^ (1 << i), sum - dept[i], n, dp));
                    }
                }
            }
        }
        dp[set] = ans;
        return ans;
    }

    int minTransfers(vector<vector<int>>& transactions) 
    {
        // 加工出来的debt数组中一定不含有0
        vector<int>&& dept = depts(transactions);
        int n = dept.size();
        int dp[1 << n];
        memset(dp, 0xff, sizeof dp);
        return n - f(dept, (1 << n) - 1, 0, n, dp);
    }
};